home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / gcc_260.zip / gcc_260 / rtlanal.c < prev    next >
C/C++ Source or Header  |  1994-05-29  |  46KB  |  1,836 lines
  1. /* Analyze RTL for C-Compiler
  2.    Copyright (C) 1987, 88, 91, 92, 93, 1994 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. GNU CC is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU CC; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. #include "config.h"
  22. #include "rtl.h"
  23.  
  24. void note_stores ();
  25. int reg_set_p ();
  26.  
  27. /* Bit flags that specify the machine subtype we are compiling for.
  28.    Bits are tested using macros TARGET_... defined in the tm.h file
  29.    and set by `-m...' switches.  Must be defined in rtlanal.c.  */
  30.  
  31. int target_flags;
  32.  
  33. /* Return 1 if the value of X is unstable
  34.    (would be different at a different point in the program).
  35.    The frame pointer, arg pointer, etc. are considered stable
  36.    (within one function) and so is anything marked `unchanging'.  */
  37.  
  38. int
  39. rtx_unstable_p (x)
  40.      rtx x;
  41. {
  42.   register RTX_CODE code = GET_CODE (x);
  43.   register int i;
  44.   register char *fmt;
  45.  
  46.   if (code == MEM)
  47.     return ! RTX_UNCHANGING_P (x);
  48.  
  49.   if (code == QUEUED)
  50.     return 1;
  51.  
  52.   if (code == CONST || code == CONST_INT)
  53.     return 0;
  54.  
  55.   if (code == REG)
  56.     return ! (REGNO (x) == FRAME_POINTER_REGNUM
  57.           || REGNO (x) == HARD_FRAME_POINTER_REGNUM
  58.           || REGNO (x) == ARG_POINTER_REGNUM
  59.           || RTX_UNCHANGING_P (x));
  60.  
  61.   fmt = GET_RTX_FORMAT (code);
  62.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  63.     if (fmt[i] == 'e')
  64.       if (rtx_unstable_p (XEXP (x, i)))
  65.     return 1;
  66.   return 0;
  67. }
  68.  
  69. /* Return 1 if X has a value that can vary even between two
  70.    executions of the program.  0 means X can be compared reliably
  71.    against certain constants or near-constants.
  72.    The frame pointer and the arg pointer are considered constant.  */
  73.  
  74. int
  75. rtx_varies_p (x)
  76.      rtx x;
  77. {
  78.   register RTX_CODE code = GET_CODE (x);
  79.   register int i;
  80.   register char *fmt;
  81.  
  82.   switch (code)
  83.     {
  84.     case MEM:
  85.     case QUEUED:
  86.       return 1;
  87.  
  88.     case CONST:
  89.     case CONST_INT:
  90.     case CONST_DOUBLE:
  91.     case SYMBOL_REF:
  92.     case LABEL_REF:
  93.       return 0;
  94.  
  95.     case REG:
  96.       /* Note that we have to test for the actual rtx used for the frame
  97.      and arg pointers and not just the register number in case we have
  98.      eliminated the frame and/or arg pointer and are using it
  99.      for pseudos.  */
  100.       return ! (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
  101.         || x == arg_pointer_rtx);
  102.  
  103.     case LO_SUM:
  104.       /* The operand 0 of a LO_SUM is considered constant
  105.      (in fact is it related specifically to operand 1).  */
  106.       return rtx_varies_p (XEXP (x, 1));
  107.     }
  108.  
  109.   fmt = GET_RTX_FORMAT (code);
  110.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  111.     if (fmt[i] == 'e')
  112.       if (rtx_varies_p (XEXP (x, i)))
  113.     return 1;
  114.   return 0;
  115. }
  116.  
  117. /* Return 0 if the use of X as an address in a MEM can cause a trap.  */
  118.  
  119. int
  120. rtx_addr_can_trap_p (x)
  121.      register rtx x;
  122. {
  123.   register enum rtx_code code = GET_CODE (x);
  124.  
  125.   switch (code)
  126.     {
  127.     case SYMBOL_REF:
  128.     case LABEL_REF:
  129.       /* SYMBOL_REF is problematic due to the possible presence of
  130.      a #pragma weak, but to say that loads from symbols can trap is
  131.      *very* costly.  It's not at all clear what's best here.  For
  132.      now, we ignore the impact of #pragma weak.  */
  133.       return 0;
  134.  
  135.     case REG:
  136.       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
  137.       return ! (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
  138.         || x == stack_pointer_rtx || x == arg_pointer_rtx);
  139.  
  140.     case CONST:
  141.       return rtx_addr_can_trap_p (XEXP (x, 0));
  142.  
  143.     case PLUS:
  144.       /* An address is assumed not to trap if it is an address that can't
  145.      trap plus a constant integer.  */
  146.       return (rtx_addr_can_trap_p (XEXP (x, 0))
  147.           || GET_CODE (XEXP (x, 1)) != CONST_INT);
  148.  
  149.     case LO_SUM:
  150.       return rtx_addr_can_trap_p (XEXP (x, 1));
  151.     }
  152.  
  153.   /* If it isn't one of the case above, it can cause a trap.  */
  154.   return 1;
  155. }
  156.  
  157. /* Return 1 if X refers to a memory location whose address 
  158.    cannot be compared reliably with constant addresses,
  159.    or if X refers to a BLKmode memory object.  */
  160.  
  161. int
  162. rtx_addr_varies_p (x)
  163.      rtx x;
  164. {
  165.   register enum rtx_code code;
  166.   register int i;
  167.   register char *fmt;
  168.  
  169.   if (x == 0)
  170.     return 0;
  171.  
  172.   code = GET_CODE (x);
  173.   if (code == MEM)
  174.     return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0));
  175.  
  176.   fmt = GET_RTX_FORMAT (code);
  177.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  178.     if (fmt[i] == 'e')
  179.       if (rtx_addr_varies_p (XEXP (x, i)))
  180.     return 1;
  181.   return 0;
  182. }
  183.  
  184. /* Return the value of the integer term in X, if one is apparent;
  185.    otherwise return 0.
  186.    Only obvious integer terms are detected.
  187.    This is used in cse.c with the `related_value' field.*/
  188.  
  189. HOST_WIDE_INT
  190. get_integer_term (x)
  191.      rtx x;
  192. {
  193.   if (GET_CODE (x) == CONST)
  194.     x = XEXP (x, 0);
  195.  
  196.   if (GET_CODE (x) == MINUS
  197.       && GET_CODE (XEXP (x, 1)) == CONST_INT)
  198.     return - INTVAL (XEXP (x, 1));
  199.   if (GET_CODE (x) == PLUS
  200.       && GET_CODE (XEXP (x, 1)) == CONST_INT)
  201.     return INTVAL (XEXP (x, 1));
  202.   return 0;
  203. }
  204.  
  205. /* If X is a constant, return the value sans apparent integer term;
  206.    otherwise return 0.
  207.    Only obvious integer terms are detected.  */
  208.  
  209. rtx
  210. get_related_value (x)
  211.      rtx x;
  212. {
  213.   if (GET_CODE (x) != CONST)
  214.     return 0;
  215.   x = XEXP (x, 0);
  216.   if (GET_CODE (x) == PLUS
  217.       && GET_CODE (XEXP (x, 1)) == CONST_INT)
  218.     return XEXP (x, 0);
  219.   else if (GET_CODE (x) == MINUS
  220.        && GET_CODE (XEXP (x, 1)) == CONST_INT)
  221.     return XEXP (x, 0);
  222.   return 0;
  223. }
  224.  
  225. /* Nonzero if register REG appears somewhere within IN.
  226.    Also works if REG is not a register; in this case it checks
  227.    for a subexpression of IN that is Lisp "equal" to REG.  */
  228.  
  229. int
  230. reg_mentioned_p (reg, in)
  231.      register rtx reg, in;
  232. {
  233.   register char *fmt;
  234.   register int i;
  235.   register enum rtx_code code;
  236.  
  237.   if (in == 0)
  238.     return 0;
  239.  
  240.   if (reg == in)
  241.     return 1;
  242.  
  243.   if (GET_CODE (in) == LABEL_REF)
  244.     return reg == XEXP (in, 0);
  245.  
  246.   code = GET_CODE (in);
  247.  
  248.   switch (code)
  249.     {
  250.       /* Compare registers by number.  */
  251.     case REG:
  252.       return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
  253.  
  254.       /* These codes have no constituent expressions
  255.      and are unique.  */
  256.     case SCRATCH:
  257.     case CC0:
  258.     case PC:
  259.       return 0;
  260.  
  261.     case CONST_INT:
  262.       return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg);
  263.       
  264.     case CONST_DOUBLE:
  265.       /* These are kept unique for a given value.  */
  266.       return 0;
  267.     }
  268.  
  269.   if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
  270.     return 1;
  271.  
  272.   fmt = GET_RTX_FORMAT (code);
  273.  
  274.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  275.     {
  276.       if (fmt[i] == 'E')
  277.     {
  278.       register int j;
  279.       for (j = XVECLEN (in, i) - 1; j >= 0; j--)
  280.         if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
  281.           return 1;
  282.     }
  283.       else if (fmt[i] == 'e'
  284.            && reg_mentioned_p (reg, XEXP (in, i)))
  285.     return 1;
  286.     }
  287.   return 0;
  288. }
  289.  
  290. /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
  291.    no CODE_LABEL insn.  */
  292.  
  293. int
  294. no_labels_between_p (beg, end)
  295.      rtx beg, end;
  296. {
  297.   register rtx p;
  298.   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
  299.     if (GET_CODE (p) == CODE_LABEL)
  300.       return 0;
  301.   return 1;
  302. }
  303.  
  304. /* Nonzero if register REG is used in an insn between
  305.    FROM_INSN and TO_INSN (exclusive of those two).  */
  306.  
  307. int
  308. reg_used_between_p (reg, from_insn, to_insn)
  309.      rtx reg, from_insn, to_insn;
  310. {
  311.   register rtx insn;
  312.  
  313.   if (from_insn == to_insn)
  314.     return 0;
  315.  
  316.   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
  317.     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
  318.     && (reg_overlap_mentioned_p (reg, PATTERN (insn))
  319.        || (GET_CODE (insn) == CALL_INSN
  320.           && (find_reg_fusage (insn, USE, reg)
  321.           || find_reg_fusage (insn, CLOBBER, reg)))))
  322.       return 1;
  323.   return 0;
  324. }
  325.  
  326. /* Nonzero if the old value of X, a register, is referenced in BODY.  If X
  327.    is entirely replaced by a new value and the only use is as a SET_DEST,
  328.    we do not consider it a reference.  */
  329.  
  330. int
  331. reg_referenced_p (x, body)
  332.      rtx x;
  333.      rtx body;
  334. {
  335.   int i;
  336.  
  337.   switch (GET_CODE (body))
  338.     {
  339.     case SET:
  340.       if (reg_overlap_mentioned_p (x, SET_SRC (body)))
  341.     return 1;
  342.  
  343.       /* If the destination is anything other than CC0, PC, a REG or a SUBREG
  344.      of a REG that occupies all of the REG, the insn references X if
  345.      it is mentioned in the destination.  */
  346.       if (GET_CODE (SET_DEST (body)) != CC0
  347.       && GET_CODE (SET_DEST (body)) != PC
  348.       && GET_CODE (SET_DEST (body)) != REG
  349.       && ! (GET_CODE (SET_DEST (body)) == SUBREG
  350.         && GET_CODE (SUBREG_REG (SET_DEST (body))) == REG
  351.         && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body))))
  352.               + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
  353.             == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body)))
  354.              + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))
  355.       && reg_overlap_mentioned_p (x, SET_DEST (body)))
  356.     return 1;
  357.       break;
  358.  
  359.     case ASM_OPERANDS:
  360.       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
  361.     if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
  362.       return 1;
  363.       break;
  364.  
  365.     case CALL:
  366.     case USE:
  367.       return reg_overlap_mentioned_p (x, body);
  368.  
  369.     case TRAP_IF:
  370.       return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
  371.  
  372.     case UNSPEC:
  373.     case UNSPEC_VOLATILE:
  374.     case PARALLEL:
  375.       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
  376.     if (reg_referenced_p (x, XVECEXP (body, 0, i)))
  377.       return 1;
  378.       break;
  379.     }
  380.  
  381.   return 0;
  382. }
  383.  
  384. /* Nonzero if register REG is referenced in an insn between
  385.    FROM_INSN and TO_INSN (exclusive of those two).  Sets of REG do
  386.    not count. */
  387.  
  388. int
  389. reg_referenced_between_p (reg, from_insn, to_insn)
  390.      rtx reg, from_insn, to_insn;
  391. {
  392.   register rtx insn;
  393.  
  394.   if (from_insn == to_insn)
  395.     return 0;
  396.  
  397.   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
  398.     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
  399.     && (reg_referenced_p (reg, PATTERN (insn))
  400.        || (GET_CODE (insn) == CALL_INSN
  401.           && find_reg_fusage (insn, USE, reg))))
  402.       return 1;
  403.   return 0;
  404. }
  405.  
  406. /* Nonzero if register REG is set or clobbered in an insn between
  407.    FROM_INSN and TO_INSN (exclusive of those two).  */
  408.  
  409. int
  410. reg_set_between_p (reg, from_insn, to_insn)
  411.      rtx reg, from_insn, to_insn;
  412. {
  413.   register rtx insn;
  414.  
  415.   if (from_insn == to_insn)
  416.     return 0;
  417.  
  418.   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
  419.     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
  420.     && reg_set_p (reg, insn))
  421.       return 1;
  422.   return 0;
  423. }
  424.  
  425. /* Internals of reg_set_between_p.  */
  426.  
  427. static rtx reg_set_reg;
  428. static int reg_set_flag;
  429.  
  430. void
  431. reg_set_p_1 (x)
  432.      rtx x;
  433. {
  434.   /* We don't want to return 1 if X is a MEM that contains a register
  435.      within REG_SET_REG.  */
  436.  
  437.   if ((GET_CODE (x) != MEM)
  438.       && reg_overlap_mentioned_p (reg_set_reg, x))
  439.     reg_set_flag = 1;
  440. }
  441.  
  442. int
  443. reg_set_p (reg, insn)
  444.      rtx reg, insn;
  445. {
  446.   rtx body = insn;
  447.  
  448.   /* We can be passed an insn or part of one.  If we are passed an insn,
  449.      check if a side-effect of the insn clobbers REG.  */
  450.   if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
  451.     {
  452.       if (FIND_REG_INC_NOTE (insn, reg)
  453.       || (GET_CODE (insn) == CALL_INSN
  454.           /* We'd like to test call_used_regs here, but rtlanal.c can't
  455.          reference that variable due to its use in genattrtab.  So
  456.          we'll just be more conservative.
  457.  
  458.          ??? Unless we could ensure that the CALL_INSN_FUNCTION_USAGE
  459.          information holds all clobbered registers.  */
  460.           && ((GET_CODE (reg) == REG
  461.            && REGNO (reg) < FIRST_PSEUDO_REGISTER)
  462.           || GET_CODE (reg) == MEM
  463.           || find_reg_fusage (insn, CLOBBER, reg))))
  464.     return 1;
  465.  
  466.       body = PATTERN (insn);
  467.     }
  468.  
  469.   reg_set_reg = reg;
  470.   reg_set_flag = 0;
  471.   note_stores (body, reg_set_p_1);
  472.   return reg_set_flag;
  473. }
  474.  
  475. /* Similar to reg_set_between_p, but check all registers in X.  Return 0
  476.    only if none of them are modified between START and END.  Return 1 if
  477.    X contains a MEM; this routine does not perform any memory aliasing.  */
  478.  
  479. int
  480. modified_between_p (x, start, end)
  481.      rtx x;
  482.      rtx start, end;
  483. {
  484.   enum rtx_code code = GET_CODE (x);
  485.   char *fmt;
  486.   int i, j;
  487.  
  488.   switch (code)
  489.     {
  490.     case CONST_INT:
  491.     case CONST_DOUBLE:
  492.     case CONST:
  493.     case SYMBOL_REF:
  494.     case LABEL_REF:
  495.       return 0;
  496.  
  497.     case PC:
  498.     case CC0:
  499.       return 1;
  500.  
  501.     case MEM:
  502.       /* If the memory is not constant, assume it is modified.  If it is
  503.      constant, we still have to check the address.  */
  504.       if (! RTX_UNCHANGING_P (x))
  505.     return 1;
  506.       break;
  507.  
  508.     case REG:
  509.       return reg_set_between_p (x, start, end);
  510.     }
  511.  
  512.   fmt = GET_RTX_FORMAT (code);
  513.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  514.     {
  515.       if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
  516.     return 1;
  517.  
  518.       if (fmt[i] == 'E')
  519.     for (j = XVECLEN (x, i) - 1; j >= 0; j--)
  520.       if (modified_between_p (XVECEXP (x, i, j), start, end))
  521.         return 1;
  522.     }
  523.  
  524.   return 0;
  525. }
  526.  
  527. /* Similar to reg_set_p, but check all registers in X.  Return 0 only if none
  528.    of them are modified in INSN.  Return 1 if X contains a MEM; this routine
  529.    does not perform any memory aliasing.  */
  530.  
  531. int
  532. modified_in_p (x, insn)
  533.      rtx x;
  534.      rtx insn;
  535. {
  536.   enum rtx_code code = GET_CODE (x);
  537.   char *fmt;
  538.   int i, j;
  539.  
  540.   switch (code)
  541.     {
  542.     case CONST_INT:
  543.     case CONST_DOUBLE:
  544.     case CONST:
  545.     case SYMBOL_REF:
  546.     case LABEL_REF:
  547.       return 0;
  548.  
  549.     case PC:
  550.     case CC0:
  551.       return 1;
  552.  
  553.     case MEM:
  554.       /* If the memory is not constant, assume it is modified.  If it is
  555.      constant, we still have to check the address.  */
  556.       if (! RTX_UNCHANGING_P (x))
  557.     return 1;
  558.       break;
  559.  
  560.     case REG:
  561.       return reg_set_p (x, insn);
  562.     }
  563.  
  564.   fmt = GET_RTX_FORMAT (code);
  565.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  566.     {
  567.       if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
  568.     return 1;
  569.  
  570.       if (fmt[i] == 'E')
  571.     for (j = XVECLEN (x, i) - 1; j >= 0; j--)
  572.       if (modified_in_p (XVECEXP (x, i, j), insn))
  573.         return 1;
  574.     }
  575.  
  576.   return 0;
  577. }
  578.  
  579. /* Given an INSN, return a SET expression if this insn has only a single SET.
  580.    It may also have CLOBBERs, USEs, or SET whose output
  581.    will not be used, which we ignore.  */
  582.  
  583. rtx
  584. single_set (insn)
  585.      rtx insn;
  586. {
  587.   rtx set;
  588.   int i;
  589.   
  590.   if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
  591.     return 0;
  592.  
  593.   if (GET_CODE (PATTERN (insn)) == SET)
  594.     return PATTERN (insn);
  595.   
  596.   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
  597.     {
  598.       for (i = 0, set = 0; i < XVECLEN (PATTERN (insn), 0); i++)
  599.     if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
  600.         && (! find_reg_note (insn, REG_UNUSED,
  601.                  SET_DEST (XVECEXP (PATTERN (insn), 0, i)))
  602.         || side_effects_p (XVECEXP (PATTERN (insn), 0, i))))
  603.       {
  604.         if (set)
  605.           return 0;
  606.         else
  607.           set = XVECEXP (PATTERN (insn), 0, i);
  608.       }
  609.       return set;
  610.     }
  611.   
  612.   return 0;
  613. }
  614.  
  615. /* Return the last thing that X was assigned from before *PINSN.  Verify that
  616.    the object is not modified up to VALID_TO.  If it was, if we hit
  617.    a partial assignment to X, or hit a CODE_LABEL first, return X.  If we
  618.    found an assignment, update *PINSN to point to it.  */
  619.  
  620. rtx
  621. find_last_value (x, pinsn, valid_to)
  622.      rtx x;
  623.      rtx *pinsn;
  624.      rtx valid_to;
  625. {
  626.   rtx p;
  627.  
  628.   for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL;
  629.        p = PREV_INSN (p))
  630.     if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
  631.       {
  632.     rtx set = single_set (p);
  633.     rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
  634.  
  635.     if (set && rtx_equal_p (x, SET_DEST (set)))
  636.       {
  637.         rtx src = SET_SRC (set);
  638.  
  639.         if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
  640.           src = XEXP (note, 0);
  641.  
  642.         if (! modified_between_p (src, PREV_INSN (p), valid_to)
  643.         /* Reject hard registers because we don't usually want
  644.            to use them; we'd rather use a pseudo.  */
  645.         && ! (GET_CODE (src) == REG
  646.               && REGNO (src) < FIRST_PSEUDO_REGISTER))
  647.           {
  648.         *pinsn = p;
  649.         return src;
  650.           }
  651.       }
  652.       
  653.     /* If set in non-simple way, we don't have a value.  */
  654.     if (reg_set_p (x, p))
  655.       break;
  656.       }
  657.  
  658.   return x;
  659. }     
  660.  
  661. /* Return nonzero if register in range [REGNO, ENDREGNO)
  662.    appears either explicitly or implicitly in X
  663.    other than being stored into.
  664.  
  665.    References contained within the substructure at LOC do not count.
  666.    LOC may be zero, meaning don't ignore anything.  */
  667.  
  668. int
  669. refers_to_regno_p (regno, endregno, x, loc)
  670.      int regno, endregno;
  671.      rtx x;
  672.      rtx *loc;
  673. {
  674.   register int i;
  675.   register RTX_CODE code;
  676.   register char *fmt;
  677.  
  678.  repeat:
  679.   /* The contents of a REG_NONNEG note is always zero, so we must come here
  680.      upon repeat in case the last REG_NOTE is a REG_NONNEG note.  */
  681.   if (x == 0)
  682.     return 0;
  683.  
  684.   code = GET_CODE (x);
  685.  
  686.   switch (code)
  687.     {
  688.     case REG:
  689.       i = REGNO (x);
  690.  
  691.       /* If we modifying the stack, frame, or argument pointer, it will
  692.      clobber a virtual register.  In fact, we could be more precise,
  693.      but it isn't worth it.  */
  694.       if ((i == STACK_POINTER_REGNUM
  695. #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
  696.        || i == ARG_POINTER_REGNUM
  697. #endif
  698.        || i == FRAME_POINTER_REGNUM)
  699.       && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
  700.     return 1;
  701.  
  702.       return (endregno > i
  703.           && regno < i + (i < FIRST_PSEUDO_REGISTER 
  704.                   ? HARD_REGNO_NREGS (i, GET_MODE (x))
  705.                   : 1));
  706.  
  707.     case SUBREG:
  708.       /* If this is a SUBREG of a hard reg, we can see exactly which
  709.      registers are being modified.  Otherwise, handle normally.  */
  710.       if (GET_CODE (SUBREG_REG (x)) == REG
  711.       && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
  712.     {
  713.       int inner_regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
  714.       int inner_endregno
  715.         = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
  716.                  ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
  717.  
  718.       return endregno > inner_regno && regno < inner_endregno;
  719.     }
  720.       break;
  721.  
  722.     case CLOBBER:
  723.     case SET:
  724.       if (&SET_DEST (x) != loc
  725.       /* Note setting a SUBREG counts as referring to the REG it is in for
  726.          a pseudo but not for hard registers since we can
  727.          treat each word individually.  */
  728.       && ((GET_CODE (SET_DEST (x)) == SUBREG
  729.            && loc != &SUBREG_REG (SET_DEST (x))
  730.            && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
  731.            && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
  732.            && refers_to_regno_p (regno, endregno,
  733.                      SUBREG_REG (SET_DEST (x)), loc))
  734.           || (GET_CODE (SET_DEST (x)) != REG
  735.           && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
  736.     return 1;
  737.  
  738.       if (code == CLOBBER || loc == &SET_SRC (x))
  739.     return 0;
  740.       x = SET_SRC (x);
  741.       goto repeat;
  742.     }
  743.  
  744.   /* X does not match, so try its subexpressions.  */
  745.  
  746.   fmt = GET_RTX_FORMAT (code);
  747.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  748.     {
  749.       if (fmt[i] == 'e' && loc != &XEXP (x, i))
  750.     {
  751.       if (i == 0)
  752.         {
  753.           x = XEXP (x, 0);
  754.           goto repeat;
  755.         }
  756.       else
  757.         if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
  758.           return 1;
  759.     }
  760.       else if (fmt[i] == 'E')
  761.     {
  762.       register int j;
  763.       for (j = XVECLEN (x, i) - 1; j >=0; j--)
  764.         if (loc != &XVECEXP (x, i, j)
  765.         && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
  766.           return 1;
  767.     }
  768.     }
  769.   return 0;
  770. }
  771.  
  772. /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
  773.    we check if any register number in X conflicts with the relevant register
  774.    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
  775.    contains a MEM (we don't bother checking for memory addresses that can't
  776.    conflict because we expect this to be a rare case.  */
  777.  
  778. int
  779. reg_overlap_mentioned_p (x, in)
  780.      rtx x, in;
  781. {
  782.   int regno, endregno;
  783.  
  784.   if (GET_CODE (x) == SUBREG)
  785.     {
  786.       regno = REGNO (SUBREG_REG (x));
  787.       if (regno < FIRST_PSEUDO_REGISTER)
  788.     regno += SUBREG_WORD (x);
  789.     }
  790.   else if (GET_CODE (x) == REG)
  791.     regno = REGNO (x);
  792.   else if (CONSTANT_P (x))
  793.     return 0;
  794.   else if (GET_CODE (x) == MEM)
  795.     {
  796.       char *fmt;
  797.       int i;
  798.  
  799.       if (GET_CODE (in) == MEM)
  800.     return 1;
  801.  
  802.       fmt = GET_RTX_FORMAT (GET_CODE (in));
  803.  
  804.       for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
  805.     if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
  806.       return 1;
  807.  
  808.       return 0;
  809.     }
  810.   else if (GET_CODE (x) == SCRATCH || GET_CODE (x) == PC
  811.        || GET_CODE (x) == CC0)
  812.     return reg_mentioned_p (x, in);
  813.   else
  814.     abort ();
  815.  
  816.   endregno = regno + (regno < FIRST_PSEUDO_REGISTER
  817.               ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
  818.  
  819.   return refers_to_regno_p (regno, endregno, in, NULL_PTR);
  820. }
  821.  
  822. /* Used for communications between the next few functions.  */
  823.  
  824. static int reg_set_last_unknown;
  825. static rtx reg_set_last_value;
  826. static int reg_set_last_first_regno, reg_set_last_last_regno;
  827.  
  828. /* Called via note_stores from reg_set_last.  */
  829.  
  830. static void
  831. reg_set_last_1 (x, pat)
  832.      rtx x;
  833.      rtx pat;
  834. {
  835.   int first, last;
  836.  
  837.   /* If X is not a register, or is not one in the range we care
  838.      about, ignore.  */
  839.   if (GET_CODE (x) != REG)
  840.     return;
  841.  
  842.   first = REGNO (x);
  843.   last = first + (first < FIRST_PSEUDO_REGISTER
  844.           ? HARD_REGNO_NREGS (first, GET_MODE (x)) : 1);
  845.  
  846.   if (first >= reg_set_last_last_regno
  847.       || last <= reg_set_last_first_regno)
  848.     return;
  849.  
  850.   /* If this is a CLOBBER or is some complex LHS, or doesn't modify
  851.      exactly the registers we care about, show we don't know the value.  */
  852.   if (GET_CODE (pat) == CLOBBER || SET_DEST (pat) != x
  853.       || first != reg_set_last_first_regno
  854.       || last != reg_set_last_last_regno)
  855.     reg_set_last_unknown = 1;
  856.   else
  857.     reg_set_last_value = SET_SRC (pat);
  858. }
  859.  
  860. /* Return the last value to which REG was set prior to INSN.  If we can't
  861.    find it easily, return 0.
  862.  
  863.    We only return a REG, SUBREG, or constant because it is too hard to
  864.    check if a MEM remains unchanged.  */
  865.  
  866. rtx
  867. reg_set_last (x, insn)
  868.      rtx x;
  869.      rtx insn;
  870. {
  871.   rtx orig_insn = insn;
  872.  
  873.   reg_set_last_first_regno = REGNO (x);
  874.  
  875.   reg_set_last_last_regno
  876.     = reg_set_last_first_regno
  877.       + (reg_set_last_first_regno < FIRST_PSEUDO_REGISTER
  878.      ? HARD_REGNO_NREGS (reg_set_last_first_regno, GET_MODE (x)) : 1);
  879.  
  880.   reg_set_last_unknown = 0;
  881.   reg_set_last_value = 0;
  882.  
  883.   /* Scan backwards until reg_set_last_1 changed one of the above flags.
  884.      Stop when we reach a label or X is a hard reg and we reach a
  885.      CALL_INSN (if reg_set_last_last_regno is a hard reg).
  886.  
  887.      If we find a set of X, ensure that its SET_SRC remains unchanged.  */
  888.  
  889.   /* We compare with <= here, because reg_set_last_last_regno
  890.      is actually the number of the first reg *not* in X.  */
  891.   for (;
  892.        insn && GET_CODE (insn) != CODE_LABEL
  893.        && ! (GET_CODE (insn) == CALL_INSN
  894.          && reg_set_last_last_regno <= FIRST_PSEUDO_REGISTER);
  895.        insn = PREV_INSN (insn))
  896.     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
  897.       {
  898.     note_stores (PATTERN (insn), reg_set_last_1);
  899.     if (reg_set_last_unknown)
  900.       return 0;
  901.     else if (reg_set_last_value)
  902.       {
  903.         if (CONSTANT_P (reg_set_last_value)
  904.         || ((GET_CODE (reg_set_last_value) == REG
  905.              || GET_CODE (reg_set_last_value) == SUBREG)
  906.             && ! reg_set_between_p (reg_set_last_value,
  907.                         NEXT_INSN (insn), orig_insn)))
  908.           return reg_set_last_value;
  909.         else
  910.           return 0;
  911.       }
  912.       }
  913.  
  914.   return 0;
  915. }
  916.  
  917. /* This is 1 until after reload pass.  */
  918. int rtx_equal_function_value_matters;
  919.  
  920. /* Return 1 if X and Y are identical-looking rtx's.
  921.    This is the Lisp function EQUAL for rtx arguments.  */
  922.  
  923. int
  924. rtx_equal_p (x, y)
  925.      rtx x, y;
  926. {
  927.   register int i;
  928.   register int j;
  929.   register enum rtx_code code;
  930.   register char *fmt;
  931.  
  932.   if (x == y)
  933.     return 1;
  934.   if (x == 0 || y == 0)
  935.     return 0;
  936.  
  937.   code = GET_CODE (x);
  938.   /* Rtx's of different codes cannot be equal.  */
  939.   if (code != GET_CODE (y))
  940.     return 0;
  941.  
  942.   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
  943.      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
  944.  
  945.   if (GET_MODE (x) != GET_MODE (y))
  946.     return 0;
  947.  
  948.   /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively.  */
  949.  
  950.   if (code == REG)
  951.     /* Until rtl generation is complete, don't consider a reference to the
  952.        return register of the current function the same as the return from a
  953.        called function.  This eases the job of function integration.  Once the
  954.        distinction is no longer needed, they can be considered equivalent.  */
  955.     return (REGNO (x) == REGNO (y)
  956.         && (! rtx_equal_function_value_matters
  957.         || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
  958.   else if (code == LABEL_REF)
  959.     return XEXP (x, 0) == XEXP (y, 0);
  960.   else if (code == SYMBOL_REF)
  961.     return XSTR (x, 0) == XSTR (y, 0);
  962.   else if (code == SCRATCH || code == CONST_DOUBLE)
  963.     return 0;
  964.  
  965.   /* Compare the elements.  If any pair of corresponding elements
  966.      fail to match, return 0 for the whole things.  */
  967.  
  968.   fmt = GET_RTX_FORMAT (code);
  969.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  970.     {
  971.       switch (fmt[i])
  972.     {
  973.     case 'w':
  974.       if (XWINT (x, i) != XWINT (y, i))
  975.         return 0;
  976.       break;
  977.  
  978.     case 'n':
  979.     case 'i':
  980.       if (XINT (x, i) != XINT (y, i))
  981.         return 0;
  982.       break;
  983.  
  984.     case 'V':
  985.     case 'E':
  986.       /* Two vectors must have the same length.  */
  987.       if (XVECLEN (x, i) != XVECLEN (y, i))
  988.         return 0;
  989.  
  990.       /* And the corresponding elements must match.  */
  991.       for (j = 0; j < XVECLEN (x, i); j++)
  992.         if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
  993.           return 0;
  994.       break;
  995.  
  996.     case 'e':
  997.       if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
  998.         return 0;
  999.       break;
  1000.  
  1001.     case 'S':
  1002.     case 's':
  1003.       if (strcmp (XSTR (x, i), XSTR (y, i)))
  1004.         return 0;
  1005.       break;
  1006.  
  1007.     case 'u':
  1008.       /* These are just backpointers, so they don't matter.  */
  1009.       break;
  1010.  
  1011.     case '0':
  1012.       break;
  1013.  
  1014.       /* It is believed that rtx's at this level will never
  1015.          contain anything but integers and other rtx's,
  1016.          except for within LABEL_REFs and SYMBOL_REFs.  */
  1017.     default:
  1018.       abort ();
  1019.     }
  1020.     }
  1021.   return 1;
  1022. }
  1023.  
  1024. /* Call FUN on each register or MEM that is stored into or clobbered by X.
  1025.    (X would be the pattern of an insn).
  1026.    FUN receives two arguments:
  1027.      the REG, MEM, CC0 or PC being stored in or clobbered,
  1028.      the SET or CLOBBER rtx that does the store.
  1029.  
  1030.   If the item being stored in or clobbered is a SUBREG of a hard register,
  1031.   the SUBREG will be passed.  */
  1032.      
  1033. void
  1034. note_stores (x, fun)
  1035.      register rtx x;
  1036.      void (*fun) ();
  1037. {
  1038.   if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER))
  1039.     {
  1040.       register rtx dest = SET_DEST (x);
  1041.       while ((GET_CODE (dest) == SUBREG
  1042.           && (GET_CODE (SUBREG_REG (dest)) != REG
  1043.           || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
  1044.          || GET_CODE (dest) == ZERO_EXTRACT
  1045.          || GET_CODE (dest) == SIGN_EXTRACT
  1046.          || GET_CODE (dest) == STRICT_LOW_PART)
  1047.     dest = XEXP (dest, 0);
  1048.       (*fun) (dest, x);
  1049.     }
  1050.   else if (GET_CODE (x) == PARALLEL)
  1051.     {
  1052.       register int i;
  1053.       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
  1054.     {
  1055.       register rtx y = XVECEXP (x, 0, i);
  1056.       if (GET_CODE (y) == SET || GET_CODE (y) == CLOBBER)
  1057.         {
  1058.           register rtx dest = SET_DEST (y);
  1059.           while ((GET_CODE (dest) == SUBREG
  1060.               && (GET_CODE (SUBREG_REG (dest)) != REG
  1061.               || (REGNO (SUBREG_REG (dest))
  1062.                   >= FIRST_PSEUDO_REGISTER)))
  1063.              || GET_CODE (dest) == ZERO_EXTRACT
  1064.              || GET_CODE (dest) == SIGN_EXTRACT
  1065.              || GET_CODE (dest) == STRICT_LOW_PART)
  1066.         dest = XEXP (dest, 0);
  1067.           (*fun) (dest, y);
  1068.         }
  1069.     }
  1070.     }
  1071. }
  1072.  
  1073. /* Return nonzero if X's old contents don't survive after INSN.
  1074.    This will be true if X is (cc0) or if X is a register and
  1075.    X dies in INSN or because INSN entirely sets X.
  1076.  
  1077.    "Entirely set" means set directly and not through a SUBREG,
  1078.    ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
  1079.    Likewise, REG_INC does not count.
  1080.  
  1081.    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
  1082.    but for this use that makes no difference, since regs don't overlap
  1083.    during their lifetimes.  Therefore, this function may be used
  1084.    at any time after deaths have been computed (in flow.c).
  1085.  
  1086.    If REG is a hard reg that occupies multiple machine registers, this
  1087.    function will only return 1 if each of those registers will be replaced
  1088.    by INSN.  */
  1089.  
  1090. int
  1091. dead_or_set_p (insn, x)
  1092.      rtx insn;
  1093.      rtx x;
  1094. {
  1095.   register int regno, last_regno;
  1096.   register int i;
  1097.  
  1098.   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
  1099.   if (GET_CODE (x) == CC0)
  1100.     return 1;
  1101.  
  1102.   if (GET_CODE (x) != REG)
  1103.     abort ();
  1104.  
  1105.   regno = REGNO (x);
  1106.   last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
  1107.         : regno + HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1);
  1108.  
  1109.   for (i = regno; i <= last_regno; i++)
  1110.     if (! dead_or_set_regno_p (insn, i))
  1111.       return 0;
  1112.  
  1113.   return 1;
  1114. }
  1115.  
  1116. /* Utility function for dead_or_set_p to check an individual register.  Also
  1117.    called from flow.c.  */
  1118.  
  1119. int
  1120. dead_or_set_regno_p (insn, test_regno)
  1121.      rtx insn;
  1122.      int test_regno;
  1123. {
  1124.   int regno, endregno;
  1125.   rtx link;
  1126.  
  1127.   /* See if there is a death note for something that includes TEST_REGNO.  */
  1128.   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
  1129.     {
  1130.       if (REG_NOTE_KIND (link) != REG_DEAD || GET_CODE (XEXP (link, 0)) != REG)
  1131.     continue;
  1132.  
  1133.       regno = REGNO (XEXP (link, 0));
  1134.       endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
  1135.           : regno + HARD_REGNO_NREGS (regno,
  1136.                           GET_MODE (XEXP (link, 0))));
  1137.  
  1138.       if (test_regno >= regno && test_regno < endregno)
  1139.     return 1;
  1140.     }
  1141.  
  1142.   if (GET_CODE (insn) == CALL_INSN
  1143.       && find_regno_fusage (insn, CLOBBER, test_regno))
  1144.     return 1;
  1145.  
  1146.   if (GET_CODE (PATTERN (insn)) == SET)
  1147.     {
  1148.       rtx dest = SET_DEST (PATTERN (insn));
  1149.  
  1150.       /* A value is totally replaced if it is the destination or the
  1151.      destination is a SUBREG of REGNO that does not change the number of
  1152.      words in it.  */
  1153.      if (GET_CODE (dest) == SUBREG
  1154.       && (((GET_MODE_SIZE (GET_MODE (dest))
  1155.         + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
  1156.           == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
  1157.            + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
  1158.     dest = SUBREG_REG (dest);
  1159.  
  1160.       if (GET_CODE (dest) != REG)
  1161.     return 0;
  1162.  
  1163.       regno = REGNO (dest);
  1164.       endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
  1165.           : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
  1166.  
  1167.       return (test_regno >= regno && test_regno < endregno);
  1168.     }
  1169.   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
  1170.     {
  1171.       register int i;
  1172.  
  1173.       for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
  1174.     {
  1175.       rtx body = XVECEXP (PATTERN (insn), 0, i);
  1176.  
  1177.       if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
  1178.         {
  1179.           rtx dest = SET_DEST (body);
  1180.  
  1181.           if (GET_CODE (dest) == SUBREG
  1182.           && (((GET_MODE_SIZE (GET_MODE (dest))
  1183.             + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
  1184.               == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
  1185.                + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
  1186.         dest = SUBREG_REG (dest);
  1187.  
  1188.           if (GET_CODE (dest) != REG)
  1189.         continue;
  1190.  
  1191.           regno = REGNO (dest);
  1192.           endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
  1193.               : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
  1194.  
  1195.           if (test_regno >= regno && test_regno < endregno)
  1196.         return 1;
  1197.         }
  1198.     }
  1199.     }
  1200.  
  1201.   return 0;
  1202. }
  1203.  
  1204. /* Return the reg-note of kind KIND in insn INSN, if there is one.
  1205.    If DATUM is nonzero, look for one whose datum is DATUM.  */
  1206.  
  1207. rtx
  1208. find_reg_note (insn, kind, datum)
  1209.      rtx insn;
  1210.      enum reg_note kind;
  1211.      rtx datum;
  1212. {
  1213.   register rtx link;
  1214.  
  1215.   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
  1216.     if (REG_NOTE_KIND (link) == kind
  1217.     && (datum == 0 || datum == XEXP (link, 0)))
  1218.       return link;
  1219.   return 0;
  1220. }
  1221.  
  1222. /* Return the reg-note of kind KIND in insn INSN which applies to register
  1223.    number REGNO, if any.  Return 0 if there is no such reg-note.  Note that
  1224.    the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
  1225.    it might be the case that the note overlaps REGNO.  */
  1226.  
  1227. rtx
  1228. find_regno_note (insn, kind, regno)
  1229.      rtx insn;
  1230.      enum reg_note kind;
  1231.      int regno;
  1232. {
  1233.   register rtx link;
  1234.  
  1235.   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
  1236.     if (REG_NOTE_KIND (link) == kind
  1237.     /* Verify that it is a register, so that scratch and MEM won't cause a
  1238.        problem here.  */
  1239.     && GET_CODE (XEXP (link, 0)) == REG
  1240.     && REGNO (XEXP (link, 0)) <= regno
  1241.     && ((REGNO (XEXP (link, 0))
  1242.          + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
  1243.         : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
  1244.                     GET_MODE (XEXP (link, 0)))))
  1245.         > regno))
  1246.       return link;
  1247.   return 0;
  1248. }
  1249.  
  1250. /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
  1251.    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
  1252.  
  1253. int
  1254. find_reg_fusage (insn, code, datum)
  1255.      rtx insn;
  1256.      enum rtx_code code;
  1257.      rtx datum;
  1258. {
  1259.   /* If it's not a CALL_INSN, it can't possibly have a
  1260.      CALL_INSN_FUNCTION_USAGE field, so don't bother checking.  */
  1261.   if (GET_CODE (insn) != CALL_INSN)
  1262.     return 0;
  1263.  
  1264.   if (! datum)
  1265.     abort();
  1266.  
  1267.   if (GET_CODE (datum) != REG)
  1268.     {
  1269.       register rtx link;
  1270.  
  1271.       for (link = CALL_INSN_FUNCTION_USAGE (insn);
  1272.            link;
  1273.        link = XEXP (link, 1))
  1274.         if (GET_CODE (XEXP (link, 0)) == code
  1275.         && rtx_equal_p (datum, SET_DEST (XEXP (link, 0))))
  1276.           return 1;
  1277.     }
  1278.   else
  1279.     {
  1280.       register int regno = REGNO (datum);
  1281.  
  1282.       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
  1283.      to pseudo registers, so don't bother checking.  */
  1284.  
  1285.       if (regno < FIRST_PSEUDO_REGISTER)
  1286.         {
  1287.       int end_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (datum));
  1288.       int i;
  1289.  
  1290.       for (i = regno; i < end_regno; i++)
  1291.         if (find_regno_fusage (insn, code, i))
  1292.           return 1;
  1293.         }
  1294.     }
  1295.  
  1296.   return 0;
  1297. }
  1298.  
  1299. /* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
  1300.    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
  1301.  
  1302. int
  1303. find_regno_fusage (insn, code, regno)
  1304.      rtx insn;
  1305.      enum rtx_code code;
  1306.      int regno;
  1307. {
  1308.   register rtx link;
  1309.  
  1310.   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
  1311.      to pseudo registers, so don't bother checking.  */
  1312.  
  1313.   if (regno >= FIRST_PSEUDO_REGISTER
  1314.       || GET_CODE (insn) != CALL_INSN )
  1315.     return 0;
  1316.  
  1317.   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
  1318.    {
  1319.     register int regnote;
  1320.     register rtx op;
  1321.  
  1322.     if (GET_CODE (op = XEXP (link, 0)) == code
  1323.     && GET_CODE (SET_DEST (op)) == REG
  1324.     && (regnote = REGNO (SET_DEST (op))) <= regno
  1325.     && regnote
  1326.         + HARD_REGNO_NREGS (regnote, GET_MODE (SET_DEST (op)))
  1327.         > regno)
  1328.       return 1;
  1329.    }
  1330.  
  1331.   return 0;
  1332. }
  1333.  
  1334. /* Remove register note NOTE from the REG_NOTES of INSN.  */
  1335.  
  1336. void
  1337. remove_note (insn, note)
  1338.      register rtx note;
  1339.      register rtx insn;
  1340. {
  1341.   register rtx link;
  1342.  
  1343.   if (REG_NOTES (insn) == note)
  1344.     {
  1345.       REG_NOTES (insn) = XEXP (note, 1);
  1346.       return;
  1347.     }
  1348.  
  1349.   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
  1350.     if (XEXP (link, 1) == note)
  1351.       {
  1352.     XEXP (link, 1) = XEXP (note, 1);
  1353.     return;
  1354.       }
  1355.  
  1356.   abort ();
  1357. }
  1358.  
  1359. /* Nonzero if X contains any volatile instructions.  These are instructions
  1360.    which may cause unpredictable machine state instructions, and thus no
  1361.    instructions should be moved or combined across them.  This includes
  1362.    only volatile asms and UNSPEC_VOLATILE instructions.  */
  1363.  
  1364. int
  1365. volatile_insn_p (x)
  1366.      rtx x;
  1367. {
  1368.   register RTX_CODE code;
  1369.  
  1370.   code = GET_CODE (x);
  1371.   switch (code)
  1372.     {
  1373.     case LABEL_REF:
  1374.     case SYMBOL_REF:
  1375.     case CONST_INT:
  1376.     case CONST:
  1377.     case CONST_DOUBLE:
  1378.     case CC0:
  1379.     case PC:
  1380.     case REG:
  1381.     case SCRATCH:
  1382.     case CLOBBER:
  1383.     case ASM_INPUT:
  1384.     case ADDR_VEC:
  1385.     case ADDR_DIFF_VEC:
  1386.     case CALL:
  1387.     case MEM:
  1388.       return 0;
  1389.  
  1390.     case UNSPEC_VOLATILE:
  1391.  /* case TRAP_IF: This isn't clear yet.  */
  1392.       return 1;
  1393.  
  1394.     case ASM_OPERANDS:
  1395.       if (MEM_VOLATILE_P (x))
  1396.     return 1;
  1397.     }
  1398.  
  1399.   /* Recursively scan the operands of this expression.  */
  1400.  
  1401.   {
  1402.     register char *fmt = GET_RTX_FORMAT (code);
  1403.     register int i;
  1404.     
  1405.     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1406.       {
  1407.     if (fmt[i] == 'e')
  1408.       {
  1409.         if (volatile_insn_p (XEXP (x, i)))
  1410.           return 1;
  1411.       }
  1412.     if (fmt[i] == 'E')
  1413.       {
  1414.         register int j;
  1415.         for (j = 0; j < XVECLEN (x, i); j++)
  1416.           if (volatile_insn_p (XVECEXP (x, i, j)))
  1417.         return 1;
  1418.       }
  1419.       }
  1420.   }
  1421.   return 0;
  1422. }
  1423.  
  1424. /* Nonzero if X contains any volatile memory references
  1425.    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
  1426.  
  1427. int
  1428. volatile_refs_p (x)
  1429.      rtx x;
  1430. {
  1431.   register RTX_CODE code;
  1432.  
  1433.   code = GET_CODE (x);
  1434.   switch (code)
  1435.     {
  1436.     case LABEL_REF:
  1437.     case SYMBOL_REF:
  1438.     case CONST_INT:
  1439.     case CONST:
  1440.     case CONST_DOUBLE:
  1441.     case CC0:
  1442.     case PC:
  1443.     case REG:
  1444.     case SCRATCH:
  1445.     case CLOBBER:
  1446.     case ASM_INPUT:
  1447.     case ADDR_VEC:
  1448.     case ADDR_DIFF_VEC:
  1449.       return 0;
  1450.  
  1451.     case CALL:
  1452.     case UNSPEC_VOLATILE:
  1453.  /* case TRAP_IF: This isn't clear yet.  */
  1454.       return 1;
  1455.  
  1456.     case MEM:
  1457.     case ASM_OPERANDS:
  1458.       if (MEM_VOLATILE_P (x))
  1459.     return 1;
  1460.     }
  1461.  
  1462.   /* Recursively scan the operands of this expression.  */
  1463.  
  1464.   {
  1465.     register char *fmt = GET_RTX_FORMAT (code);
  1466.     register int i;
  1467.     
  1468.     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1469.       {
  1470.     if (fmt[i] == 'e')
  1471.       {
  1472.         if (volatile_refs_p (XEXP (x, i)))
  1473.           return 1;
  1474.       }
  1475.     if (fmt[i] == 'E')
  1476.       {
  1477.         register int j;
  1478.         for (j = 0; j < XVECLEN (x, i); j++)
  1479.           if (volatile_refs_p (XVECEXP (x, i, j)))
  1480.         return 1;
  1481.       }
  1482.       }
  1483.   }
  1484.   return 0;
  1485. }
  1486.  
  1487. /* Similar to above, except that it also rejects register pre- and post-
  1488.    incrementing.  */
  1489.  
  1490. int
  1491. side_effects_p (x)
  1492.      rtx x;
  1493. {
  1494.   register RTX_CODE code;
  1495.  
  1496.   code = GET_CODE (x);
  1497.   switch (code)
  1498.     {
  1499.     case LABEL_REF:
  1500.     case SYMBOL_REF:
  1501.     case CONST_INT:
  1502.     case CONST:
  1503.     case CONST_DOUBLE:
  1504.     case CC0:
  1505.     case PC:
  1506.     case REG:
  1507.     case SCRATCH:
  1508.     case ASM_INPUT:
  1509.     case ADDR_VEC:
  1510.     case ADDR_DIFF_VEC:
  1511.       return 0;
  1512.  
  1513.     case CLOBBER:
  1514.       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
  1515.      when some combination can't be done.  If we see one, don't think
  1516.      that we can simplify the expression.  */
  1517.       return (GET_MODE (x) != VOIDmode);
  1518.  
  1519.     case PRE_INC:
  1520.     case PRE_DEC:
  1521.     case POST_INC:
  1522.     case POST_DEC:
  1523.     case CALL:
  1524.     case UNSPEC_VOLATILE:
  1525.  /* case TRAP_IF: This isn't clear yet.  */
  1526.       return 1;
  1527.  
  1528.     case MEM:
  1529.     case ASM_OPERANDS:
  1530.       if (MEM_VOLATILE_P (x))
  1531.     return 1;
  1532.     }
  1533.  
  1534.   /* Recursively scan the operands of this expression.  */
  1535.  
  1536.   {
  1537.     register char *fmt = GET_RTX_FORMAT (code);
  1538.     register int i;
  1539.     
  1540.     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1541.       {
  1542.     if (fmt[i] == 'e')
  1543.       {
  1544.         if (side_effects_p (XEXP (x, i)))
  1545.           return 1;
  1546.       }
  1547.     if (fmt[i] == 'E')
  1548.       {
  1549.         register int j;
  1550.         for (j = 0; j < XVECLEN (x, i); j++)
  1551.           if (side_effects_p (XVECEXP (x, i, j)))
  1552.         return 1;
  1553.       }
  1554.       }
  1555.   }
  1556.   return 0;
  1557. }
  1558.  
  1559. /* Return nonzero if evaluating rtx X might cause a trap.  */
  1560.  
  1561. int
  1562. may_trap_p (x)
  1563.      rtx x;
  1564. {
  1565.   int i;
  1566.   enum rtx_code code;
  1567.   char *fmt;
  1568.  
  1569.   if (x == 0)
  1570.     return 0;
  1571.   code = GET_CODE (x);
  1572.   switch (code)
  1573.     {
  1574.       /* Handle these cases quickly.  */
  1575.     case CONST_INT:
  1576.     case CONST_DOUBLE:
  1577.     case SYMBOL_REF:
  1578.     case LABEL_REF:
  1579.     case CONST:
  1580.     case PC:
  1581.     case CC0:
  1582.     case REG:
  1583.     case SCRATCH:
  1584.       return 0;
  1585.  
  1586.       /* Conditional trap can trap!  */
  1587.     case UNSPEC_VOLATILE:
  1588.     case TRAP_IF:
  1589.       return 1;
  1590.  
  1591.       /* Memory ref can trap unless it's a static var or a stack slot.  */
  1592.     case MEM:
  1593.       return rtx_addr_can_trap_p (XEXP (x, 0));
  1594.  
  1595.       /* Division by a non-constant might trap.  */
  1596.     case DIV:
  1597.     case MOD:
  1598.     case UDIV:
  1599.     case UMOD:
  1600.       if (! CONSTANT_P (XEXP (x, 1)))
  1601.     return 1;
  1602.       /* This was const0_rtx, but by not using that,
  1603.      we can link this file into other programs.  */
  1604.       if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) == 0)
  1605.     return 1;
  1606.     default:
  1607.       /* Any floating arithmetic may trap.  */
  1608.       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
  1609.     return 1;
  1610.     }
  1611.  
  1612.   fmt = GET_RTX_FORMAT (code);
  1613.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1614.     {
  1615.       if (fmt[i] == 'e')
  1616.     {
  1617.       if (may_trap_p (XEXP (x, i)))
  1618.         return 1;
  1619.     }
  1620.       else if (fmt[i] == 'E')
  1621.     {
  1622.       register int j;
  1623.       for (j = 0; j < XVECLEN (x, i); j++)
  1624.         if (may_trap_p (XVECEXP (x, i, j)))
  1625.           return 1;
  1626.     }
  1627.     }
  1628.   return 0;
  1629. }
  1630.  
  1631. /* Return nonzero if X contains a comparison that is not either EQ or NE,
  1632.    i.e., an inequality.  */
  1633.  
  1634. int
  1635. inequality_comparisons_p (x)
  1636.      rtx x;
  1637. {
  1638.   register char *fmt;
  1639.   register int len, i;
  1640.   register enum rtx_code code = GET_CODE (x);
  1641.  
  1642.   switch (code)
  1643.     {
  1644.     case REG:
  1645.     case SCRATCH:
  1646.     case PC:
  1647.     case CC0:
  1648.     case CONST_INT:
  1649.     case CONST_DOUBLE:
  1650.     case CONST:
  1651.     case LABEL_REF:
  1652.     case SYMBOL_REF:
  1653.       return 0;
  1654.  
  1655.     case LT:
  1656.     case LTU:
  1657.     case GT:
  1658.     case GTU:
  1659.     case LE:
  1660.     case LEU:
  1661.     case GE:
  1662.     case GEU:
  1663.       return 1;
  1664.     }
  1665.  
  1666.   len = GET_RTX_LENGTH (code);
  1667.   fmt = GET_RTX_FORMAT (code);
  1668.  
  1669.   for (i = 0; i < len; i++)
  1670.     {
  1671.       if (fmt[i] == 'e')
  1672.     {
  1673.       if (inequality_comparisons_p (XEXP (x, i)))
  1674.         return 1;
  1675.     }
  1676.       else if (fmt[i] == 'E')
  1677.     {
  1678.       register int j;
  1679.       for (j = XVECLEN (x, i) - 1; j >= 0; j--)
  1680.         if (inequality_comparisons_p (XVECEXP (x, i, j)))
  1681.           return 1;
  1682.     }
  1683.     }
  1684.         
  1685.   return 0;
  1686. }
  1687.  
  1688. /* Replace any occurrence of FROM in X with TO.
  1689.  
  1690.    Note that copying is not done so X must not be shared unless all copies
  1691.    are to be modified.  */
  1692.  
  1693. rtx
  1694. replace_rtx (x, from, to)
  1695.      rtx x, from, to;
  1696. {
  1697.   register int i, j;
  1698.   register char *fmt;
  1699.  
  1700.   if (x == from)
  1701.     return to;
  1702.  
  1703.   /* Allow this function to make replacements in EXPR_LISTs.  */
  1704.   if (x == 0)
  1705.     return 0;
  1706.  
  1707.   fmt = GET_RTX_FORMAT (GET_CODE (x));
  1708.   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
  1709.     {
  1710.       if (fmt[i] == 'e')
  1711.     XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
  1712.       else if (fmt[i] == 'E')
  1713.     for (j = XVECLEN (x, i) - 1; j >= 0; j--)
  1714.       XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
  1715.     }
  1716.  
  1717.   return x;
  1718. }  
  1719.  
  1720. /* Throughout the rtx X, replace many registers according to REG_MAP.
  1721.    Return the replacement for X (which may be X with altered contents).
  1722.    REG_MAP[R] is the replacement for register R, or 0 for don't replace.
  1723.    NREGS is the length of REG_MAP; regs >= NREGS are not mapped.  
  1724.  
  1725.    We only support REG_MAP entries of REG or SUBREG.  Also, hard registers
  1726.    should not be mapped to pseudos or vice versa since validate_change
  1727.    is not called.
  1728.  
  1729.    If REPLACE_DEST is 1, replacements are also done in destinations;
  1730.    otherwise, only sources are replaced.  */
  1731.  
  1732. rtx
  1733. replace_regs (x, reg_map, nregs, replace_dest)
  1734.      rtx x;
  1735.      rtx *reg_map;
  1736.      int nregs;
  1737.      int replace_dest;
  1738. {
  1739.   register enum rtx_code code;
  1740.   register int i;
  1741.   register char *fmt;
  1742.  
  1743.   if (x == 0)
  1744.     return x;
  1745.  
  1746.   code = GET_CODE (x);
  1747.   switch (code)
  1748.     {
  1749.     case SCRATCH:
  1750.     case PC:
  1751.     case CC0:
  1752.     case CONST_INT:
  1753.     case CONST_DOUBLE:
  1754.     case CONST:
  1755.     case SYMBOL_REF:
  1756.     case LABEL_REF:
  1757.       return x;
  1758.  
  1759.     case REG:
  1760.       /* Verify that the register has an entry before trying to access it.  */
  1761.       if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
  1762.     {
  1763.       /* SUBREGs can't be shared.  Always return a copy to ensure that if
  1764.          this replacement occurs more than once then each instance will
  1765.          get distinct rtx.  */
  1766.       if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
  1767.         return copy_rtx (reg_map[REGNO (x)]);
  1768.       return reg_map[REGNO (x)];
  1769.     }
  1770.       return x;
  1771.  
  1772.     case SUBREG:
  1773.       /* Prevent making nested SUBREGs.  */
  1774.       if (GET_CODE (SUBREG_REG (x)) == REG && REGNO (SUBREG_REG (x)) < nregs
  1775.       && reg_map[REGNO (SUBREG_REG (x))] != 0
  1776.       && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
  1777.     {
  1778.       rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
  1779.       rtx map_inner = SUBREG_REG (map_val);
  1780.  
  1781.       if (GET_MODE (x) == GET_MODE (map_inner))
  1782.         return map_inner;
  1783.       else
  1784.         {
  1785.           /* We cannot call gen_rtx here since we may be linked with
  1786.          genattrtab.c.  */
  1787.           /* Let's try clobbering the incoming SUBREG and see
  1788.          if this is really safe.  */
  1789.           SUBREG_REG (x) = map_inner;
  1790.           SUBREG_WORD (x) += SUBREG_WORD (map_val);
  1791.           return x;
  1792. #if 0
  1793.           rtx new = rtx_alloc (SUBREG);
  1794.           PUT_MODE (new, GET_MODE (x));
  1795.           SUBREG_REG (new) = map_inner;
  1796.           SUBREG_WORD (new) = SUBREG_WORD (x) + SUBREG_WORD (map_val);
  1797. #endif
  1798.         }
  1799.     }
  1800.       break;
  1801.  
  1802.     case SET:
  1803.       if (replace_dest)
  1804.     SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
  1805.  
  1806.       else if (GET_CODE (SET_DEST (x)) == MEM
  1807.            || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
  1808.     /* Even if we are not to replace destinations, replace register if it
  1809.        is CONTAINED in destination (destination is memory or
  1810.        STRICT_LOW_PART).  */
  1811.     XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
  1812.                            reg_map, nregs, 0);
  1813.       else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
  1814.     /* Similarly, for ZERO_EXTRACT we replace all operands.  */
  1815.     break;
  1816.  
  1817.       SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
  1818.       return x;
  1819.     }
  1820.  
  1821.   fmt = GET_RTX_FORMAT (code);
  1822.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1823.     {
  1824.       if (fmt[i] == 'e')
  1825.     XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
  1826.       if (fmt[i] == 'E')
  1827.     {
  1828.       register int j;
  1829.       for (j = 0; j < XVECLEN (x, i); j++)
  1830.         XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
  1831.                           nregs, replace_dest);
  1832.     }
  1833.     }
  1834.   return x;
  1835. }
  1836.